/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2024-10-14
 * Time: 15:15
 */
public class Sort {
    public static void quickSort(int[] array){
        quick(array, 0, array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        //递归条件
        if(start >= end){
            return;
        }

        //当排序组合越短时，用直接排序更快
        if(end - start + 1 <= 7){
            insertSortRange(array, start, end);
            return;
        }

        //三步取中法，把第一个数字换为数组的中位数来排序，加快对于有序数组的排序
        int minIndex = getMiddleNum(array, start, end);
        swap(array, start, minIndex);

        int pivot = partition(array, start, end);
        quick(array, start, pivot-1);
        quick(array, pivot+1, end);
    }

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];

        while(left < right){
            while(left < right && array[right] >= tmp){
                right--;
            }
            array[left] = array[right];

            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }


    private static int getMiddleNum(int[] array, int left, int right) {
        int mid = (left+right)/2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[right] < array[mid]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[right] < array[mid]){
                return right;
            }else{
                return mid;
            }
        }
    }

    private static void insertSortRange(int[] array, int start, int end) {
        for (int i = start+1; i <= end ; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= start; j--) {
                if(array[j] > array[j+1]){
                    array[j+1] = array[j];
                }else{
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    private static void swap(int[] array, int start, int end) {
        int tmp = array[start];
        array[start] = array[end];
        array[end] = tmp;
    }

    public static void mergeSort(int[] array){
        mergeSortTmp(array, 0, array.length-1);
    }

    private static void mergeSortTmp(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = (left+right) / 2;
        mergeSortTmp(array, left ,mid-1);
        mergeSortTmp(array, mid+1, right);

        merge(array, left, mid, right);
    }


    //合并两个有序数组
    private static void merge(int[] array, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;

        while(s1 <= e1 && s2 <= e2){
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        while(s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }

    public static void mergeSortNor(int[] array){
        int gap = 1;
        while(gap < array.length){
            for (int i = 0; i < array.length; i = i+gap*2) {
                int left = i;
                int mid =(left + gap-1);
                //确保mid和right不会越界
                if(mid >= array.length){
                    mid = array.length-1;
                }
                int right = mid + gap;
                if(right > array.length){
                    right = array.length-1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    public static void countSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];

        for (int i = 1; i < array.length; i++) {
            if(array[i] > maxVal){
                maxVal = array[i];
            }

            if(array[i] < minVal){
                minVal = array[i];
            }
        }

        int len = maxVal - minVal + 1;
        int[] count = new int[len];

        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index - minVal]++;
        }

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i] != 0){
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }
}
